﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace CSharpAlgorithm.Base
{
    /// <summary>
    /// 다익스트라 알고리즘
    /// 특정 노드에서 모든 모드로의 최단거리
    /// O(E * logV)
    /// </summary>
    public class Dijkstra
    {
        int V;
        List<Edge>[] G;
        int[] d;
        int[] prev;
        PriorityQueue<Pair> que;
        public Dijkstra(List<Edge>[] G, int V)
        {
            this.G = G;
            this.V = V;
            G = new List<Edge>[V + 1];
            d = new int[V + 1];
            prev = new int[V + 1];
            for (int i = 0; i < prev.Length; i++)
            {
                prev[i] = -1;
            }
            que = new PriorityQueue<Pair>(V);
        }

        /// <summary>
        /// s로부터 모든 경로의 최단거리를 구한다
        /// </summary>
        /// <param name="s"></param>
        /// <returns></returns>
        public int[] ShortestPath(int s)
        {
            for (int i = 1; i <= V; i++)
            {
                d[i] = int.MaxValue;
            }
            d[s] = 0;

            que.Push(new Pair(0, s));

            while (!que.Empty)
            {
                Pair p = que.Pop();
                int v = p.Second;
                if (d[v] < p.First)
                {
                    continue;
                }
                for (int i = 0; i < G[v].Count; i++)
                {
                    Edge e = G[v][i];
                    if (d[e.To] > d[v] + e.Cost)
                    {
                        d[e.To] = d[v] + e.Cost;
                        prev[e.To] = v;
                        que.Push(new Pair(d[e.To], e.To));
                    }
                }
            }
            return d;
        }

        /// <summary>
        /// t 까지의 최단경로
        /// </summary>
        /// <param name="t"></param>
        /// <returns></returns>
        public List<int> GetPath(int t)
        {
            List<int> path = new List<int>();
            for (; t != -1; t = prev[t])
            {
                path.Add(t);
            }
            path.Reverse();
            return path;
        }
    }
}
